package DataStructure.SortMethod;

import java.util.Arrays;

/**
 * @time: 2021/4/27/027 21:12
 * @author: Zhurunhe
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {99, 52, 3, 51, 6, 13};
        System.out.println("arr:" + Arrays.toString(arr));
        insertSort(arr);
    }

    public static void insertSort(int[] arr) {
        int insertValue, insertIndex;
        for (int i = 1; i < arr.length; i++) {
            //arr:[99, 52, 3, 51, 6, 13]
            //第1轮:[52, 99, 3, 51, 6, 13]
            //第2轮:[3, 52, 99, 51, 6, 13]
            //第3轮:[3, 51, 52, 99, 6, 13]
            //第4轮:[3, 6, 51, 52, 99, 13]
            //第5轮:[3, 6, 13, 51, 52, 99]
            insertValue = arr[i];//需要插入的数
            insertIndex = i - 1;//插入的数的前一个下标 循环中需要不断地与前一个数相比
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                //insertIndex >= 0 判断插入位置，不越界
                //insertValue < arr[insertIndex] 待插入的数，
                // 还没有找到插入的位置，insertIndex就需要后移
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //退出了while循环 就说明找到位置
            // 而且比该数大的数已经通过arr[insertIndex + 1] = arr[insertIndex]; 移动到后面
            //最后就是将带插入的数插入对应的位置
            //insertIndex+1==i 表示的待插入的数下标没有发现变化 也就是不需要移动数据
            if (insertIndex+1!=i){
                arr[insertIndex + 1] = insertValue;
            }
            System.out.println("第" + i + "轮:" + Arrays.toString(arr));
        }
        /*
        //2
        insertValue = arr[2];
        insertIndex = 2 - 1;//1
        while (insertIndex>=0&&insertValue<arr[insertIndex]){
            arr[insertIndex+1]=arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex+1]=insertValue;
        System.out.println("第"+2+"轮:"+ Arrays.toString(arr));
        //3
        insertValue = arr[3];
        insertIndex = 3 - 1;
        while (insertIndex>=0&&insertValue<arr[insertIndex]){
            arr[insertIndex+1]=arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex+1]=insertValue;
        System.out.println("第"+3+"轮:"+ Arrays.toString(arr));
        //4
        insertValue = arr[4];
        insertIndex = 4 - 1;
        while (insertIndex>=0&&insertValue<arr[insertIndex]){
            arr[insertIndex+1]=arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex+1]=insertValue;
        System.out.println("第"+4+"轮:"+ Arrays.toString(arr));
        //5
        insertValue = arr[5];
        insertIndex = 5 - 1;
        while (insertIndex>=0&&insertValue<arr[insertIndex]){
            arr[insertIndex+1]=arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex+1]=insertValue;
        System.out.println("第"+5+"轮:"+ Arrays.toString(arr));
        */
    }
}
